Many software applications exist to help users create and edit images and videos using a wide array of editing tools. Such tools range in functionality from rudimentary resizing and cropping to more complex lighting adjustments and object manipulation. Patch matching is one process often used in image editing software. Patch matching searches for parts of an image that share one or more attributes. Patch matching techniques allow for removing undesired objects from an image, in-painting new objects to match the image, stereo matching, texture synthesis, and altering a digital image in any number of ways.
Patch matching searches for similar image patches based on spatial coherence. In particular, conventional patch matching is based on using random sampling to find good matches and using natural coherence in the imagery to propagate such matches quickly to surrounding areas. Conventional patch matching scans over respective image patches of a digital image and computes a distance or similarity score. One such similarity score involves a sum-of-squares distances between pixel values. Identical patches (i.e., matches) have a sum-of-squares distance of zero. In general, finding the best patch matches for every pixel in the image requires making a large number of sum-of-squares distance evaluations.
While patch matching is faster than a brute force search, problems exist with conventional patch matching techniques. For example, conventional patch matching is slow in large search spaces. The speed of conventional patch matching further slows when allowing for patch rotation and scaling (i.e., using generalized patch match) due to the high dimensionality of the search space.